package leetcode.hot100;

public class Solution208 {
    public static void main(String[] args) {

        Trie obj = new Trie();
//        System.out.println(obj.trie[0]);
        obj.insert("apple");
        System.out.println(obj.search("apple"));
        System.out.println(obj.search("app"));
        System.out.println(obj.startsWith("app"));
        obj.insert("app");
        System.out.println(obj.search("app"));
    }
}

//class Trie {
//
//    TreeSet<String> treeSet;
//
//    /**
//     * Initialize your data structure here.
//     */
//    public Trie() {
//        treeSet = new TreeSet<>();
//    }
//
//    /**
//     * Inserts a word into the trie.
//     */
//    public void insert(String word) {
//        treeSet.add(word);
//    }
//
//    /**
//     * Returns if the word is in the trie.
//     */
//    public boolean search(String word) {
//        return treeSet.contains(word);
//    }
//
//    /**
//     * Returns if there is any word in the trie that starts with the given prefix.
//     */
//    public boolean startsWith(String prefix) {
//        //找prefix的上下限
//        String upper = treeSet.ceiling(prefix);
//        if(upper.startsWith(prefix)) return true;
//        String lower = treeSet.floor(prefix);
//        if(lower.startsWith(prefix)) return true;
//        return false;
//    }
//}

class Trie{

    TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode cur = root;
        for (int i=0;i<word.length();i++){
            int idx = word.charAt(i)-'a';
            if(cur.trieNodes[idx]==null){ //子节点不存在
                cur.trieNodes[idx] = new TrieNode();
            }
            //按当前遍历到的字符转移
            cur = cur.trieNodes[idx];
        }
        //字符串结束了，当前节点标识结束
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i)-'a';
            if(cur.trieNodes[idx]==null) return false;
            cur = cur.trieNodes[idx];
        }
        //字符串走完了
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i)-'a';
            if(cur.trieNodes[idx]==null) return false;
            cur = cur.trieNodes[idx];
        }
        //字符串走完了
        return true;
    }
}

class TrieNode{
    boolean isEnd;
    TrieNode[] trieNodes;

    public TrieNode(){
        isEnd = false;
        trieNodes = new TrieNode[25];
    }
}